//
// Created by hcDarren on 2018/10/27.
// 红黑树，实现插入操作。

#ifndef NDK_DAY47_MAP_H
#define NDK_DAY47_MAP_H
#include <queue>
using namespace std;

// 能用到的语法用一用，使用bool定义。别名rb_color
typedef bool rb_color;
#define black false // 黑色
#define red true //  红色


template<class K, class V>
class map {
private:
    struct TreeNode; // 节点
    int count;
    TreeNode *root; // 根节点，必须黑色

public:
    map() : root(NULL) {
        count = 0;
    }
public:
    struct iterator; // 迭代器
    TreeNode *parent(TreeNode *pNode) { // 父节点
        return pNode ? pNode->parent : NULL;
    }
    TreeNode *left(TreeNode *pNode) { // 左右子树
        return pNode ? pNode->left : NULL;
    }
    TreeNode *right(TreeNode *pNode) {
        return pNode ? pNode->right : NULL;
    }
    TreeNode *brother(TreeNode *pNode) { // 兄弟节点：当前节点是右儿子节点，拿左儿子节点；当前节点是左儿子节点，拿右儿子节点。
        return left(parent(pNode)) == pNode ? right(parent(pNode)) : left(parent(pNode));
    }

    rb_color getColor(TreeNode *pNode) { // 获取节点颜色,设置节点颜色
        return pNode ? pNode->color : black;
    }
    void setColor(TreeNode *pNode, rb_color color) {
        if (pNode) {
            pNode->color = color;
        }
    }

    TreeNode *L_Rotation(TreeNode *pNode) { // 左旋
        // avl 左旋 , 多了一个父亲节点
        TreeNode *right = pNode->right; // 右节点作为新的根节点
        pNode->right = right->left;     // 新根节点原来的左孩子，作为原根节点的右孩子。
        right->left = pNode;            // 原根节点，作为新根节点的左孩子。

        // 调整 pNode 父亲的儿子指向
        if (pNode->parent == NULL) {
            root = right; // 成为根节点
        } else if (pNode->parent->left == pNode) { // pNode原来是父亲的左儿子
            pNode->parent->left = right;
        } else {
            pNode->parent->right = right;
        }

        // 调整各大节点的父亲
        right->parent = pNode->parent;
        if (pNode->right) {
            pNode->right->parent = pNode;
        }
        pNode->parent = right;

        return right;
    }

    TreeNode *R_Rotation(TreeNode *pNode) {
        TreeNode *left = pNode->left;
        pNode->left = left->right;
        left->right = pNode;

        // 调整 pNode 父亲的儿子指向
        if (pNode->parent == NULL) {
            root = left;
        } else if (pNode->parent->left == pNode) {
            pNode->parent->left = left;
        } else {
            pNode->parent->right = left;
        }

        // 调整各大节点的父亲
        left->parent = pNode->parent;
        if (pNode->left) {
            pNode->left->parent = pNode;
        }
        pNode->parent = left;

        return left;
    }

    // 双红修正：不能违背性质4和5，基于这两点来解决。
    void solveDoubleRed(TreeNode *pNode) {
        while (pNode->parent && pNode->parent->color == red) { // 情况1
            if (getColor(brother(parent(pNode))) == red) { // 情况 2
                // 2.叔叔节点是红色的，把叔叔节点染黑，把父亲节点染黑，然后指针回溯至爷爷节点（交给爷爷去处理），把爷爷染红。
                setColor(parent(pNode), black);
                setColor(brother(parent(pNode)), black);
                setColor(parent(parent(pNode)), red);
                pNode = parent(parent(pNode));
            } else { // 情况 3：叔叔节点是黑色
                if (left(parent(parent(pNode))) == parent(pNode)) { // 爷爷的左儿子，是我的父节点。
                    if (right(parent(pNode)) == pNode) { // 情况 3.1: 先以父节点左旋
                        pNode = parent(pNode);
                        L_Rotation(pNode); // 以父节点左旋
                    }
                    // 情况 3.2  把我父亲这棵子树上的红色节点，挪动到我的叔叔的那棵树上
                    setColor(parent(pNode), black);
                    setColor(parent(parent(pNode)), red);
                    R_Rotation(parent(parent(pNode)));

                } else { // 爷爷的右儿子，是我的父节点。
                    if (left(parent(pNode)) == pNode) { // 情况 3.1
                        pNode = parent(pNode);
                        R_Rotation(pNode);
                    }
                    // 情况 3.2  把我父亲这棵子树上的红色节点，挪动到我的叔叔的那棵树上
                    setColor(parent(pNode), black);
                    setColor(parent(parent(pNode)), red);
                    L_Rotation(parent(parent(pNode)));
                }
            }
        }
        root->color = black; // 根节点是黑色
    }

    // 插入节点。
    iterator insert(K key, V value) {
        // 插入算法
        if (root == NULL) {
            root = new TreeNode(NULL, NULL, NULL, key, value, black);
            count = 1;
            return iterator(root);
        }

        // 最好我们插入红色节点，它不会违反性质 5 ，但是有可能会违反性质 4
        TreeNode *node = root;
        TreeNode *parent = NULL; // 循环，找到待关联的父节点
        do {
            parent = node;
            if (key == node->key) { // 找到，仅更新值
                node->value = value;
                return iterator(node);
            } else if (key > node->key) { // 新key比根节点的key大，往右边子树找
                node = node->right;
            } else { //新key比根节点的key小，往左边子树找
                node = node->left;
            }
        } while (node);

        TreeNode *new_node = new TreeNode(NULL, NULL, parent, key, value, red); // 新增红色节点
        if (key > parent->key) { // 连接起来，放在右边
            parent->right = new_node;
        } else { // 放在左边
            parent->left = new_node;
        }

        solveDoubleRed(new_node); // 解决双红节点问题。
        return iterator(new_node); // 返回迭代器
    }

    bool remove(K key) {

    }
    int size() {
        return count;
    }
    bool isEmpty() {
        return count == 0;
    }

    // 层序遍历 打印。
    void levelTraverse(void (*fun)(K, V, bool)) {
        if (root == NULL) {
            return;
        }
        TreeNode *node = root;
        queue<TreeNode *> nodes;
        nodes.push(node);
        while (!nodes.empty()) {
            node = nodes.front();
            fun(node->key, node->value, node->color);
            nodes.pop();

            if (node->left) {
                nodes.push(node->left);
            }
            if (node->right) {
                nodes.push(node->right);
            }
        }
    }
};

template<class K, class V>
struct map<K, V>::TreeNode {
public:
    TreeNode *left;   // 左子树
    TreeNode *right;  // 右子树
    TreeNode *parent; // 父节点(添加要用父节点做判断)
    K key;
    V value;
    // 节点颜色
    rb_color color;
public:
    // 构造函数，第二种方式初始化
    TreeNode(TreeNode *left, TreeNode *right, TreeNode *parent, K key, V value, rb_color color)
            :
            left(left), right(right), parent(parent), key(key), value(value), color(color) {}

    // 找到前驱（前面的点）：左边子树的最大值
    TreeNode *precursor() {
        // 参考下面successor()，做类似逻辑调整。方向相反。代码未验证。
        if(left){
            TreeNode *node = left;
            if (node->right) {
                node = node->right; // 不断往右边找
            }
            return node;
        } else {
            // 对56来讲，50才是它的前驱。
            TreeNode *successor = this;
            while (successor->parent && successor->parent->left == successor) {
                successor = successor->parent; // 一直找右上角的父节点。
            }
            return successor->parent; // 再往上走一层，找到目标。
        }
    }

    // 找后继，后面的点。
    TreeNode *successor() {
        if (right) { // 右边不为空。
            TreeNode *successor = right;
            while (successor->left) {
                successor = successor->left;
            }
            return successor;
        } else { // 不断地找父亲节点，直到找到是父亲的左儿子。在往上走一层。
            // 48找后继节点，目标要找到50，要不断地往父节点找
            TreeNode *successor = this;
            while (successor->parent && successor->parent->right == successor) {
                successor = successor->parent; // 一直找左上角的父节点
            }
            return successor->parent; // 再往上走一层，找到目标50.
        }
    }
};

template<class K, class V>
struct map<K, V>::iterator { // 迭代器，复写操作符--，++
private:
    TreeNode *node;
public:
    // 构造函数
    iterator(TreeNode *node) : node(node) {}

    iterator &operator--() {// 找前驱节点，返回迭代器，能再次--。
        node = node->precursor();
        return *this;
    }
    iterator &operator++() {// 找后继节点
        node = node->successor();
        return *this;
    }

    V operator*() { // 取节点的值
        return node->value;
    }
};
#endif //NDK_DAY47_MAP_H
